package com.formula.datastructure.exercise.sort.adv;

import com.formula.datastructure.util.DataUtil;

public class HeapSort {

    private Integer[] tree;
    private int lastIdx = -1;

    /**
     *
     * @param array
     * @return 排序要用大顶堆
     */
    public Integer[] sort(Integer[] array) {
        int N = array.length;

        // 就是从最后一个父节点开始, 倒回去, 这样排出来的一定是最大的在上面
        for (int i = N / 2; i >= 0; i--) {
            siftDown(array, i, N);
        }

        Integer temp;

        /**
         * 思想是, 最大的就是array[0], 把它和未排序的末尾交换
         * 交换后, 重排得到最大的在array[0]
         */
        for (int i = N - 1; i > 0; i--) {
            // 这一定是最大的
            temp = array[0];
            array[0] = array[i];
            array[i] = temp;

            // 这里是i-1
            siftDown(array, 0, i - 1);
        }

        return array;
    }

    /**
     * while的写法要通俗易懂太多
     * @param array
     * @param idx
     * @param length
     */
    public void siftDown(Integer[] array, int idx, int length) {
        Integer temp;
        while (getLeft(idx) < length) {
            int i = getLeft(idx);
            if (i + 1 < length && array[i + 1] > array[i]) {
                i = i + 1;
            }
            if (array[idx] >= array[i]) {
                break;
            } else {
                temp = array[idx];
                array[idx] = array[i];
                array[i] = temp;
                idx = i;
            }
        }
    }


    // 大顶堆
    private void siftDow2(Integer[] array, int idx, int len) {
        Integer temp = array[idx];
        // 从左子树开始
        for (int i = getLeft(idx); i < len; i = getLeft(i)) {
            // 找出左右子树最大的
            if (i + 1 < len && array[i] < array[i + 1]) {
                i++;
            }
            // 如果比左右子树大, 就不用继续了
            if (temp > array[i]) {
                break;
            } else {
                // 与孩子交换, 并记录下最新坐标
                array[idx] = array[i];
                idx = i;
            }
        }
        // 赋值回去
        array[idx] = temp;
    }


    private Integer getMin() {
        Integer item = tree[0];
        tree[0] = tree[lastIdx];
        tree[lastIdx--] = null;
        siftDown(0);
        return item;
    }

    private void addNode(Integer node) {
        tree[++lastIdx] = node;
        if (lastIdx > 0) {
            siftUp(lastIdx);
        }
    }

    private void siftUp(int idx) {
        while (getParent(idx) >= 0) {
            if (tree[idx] < tree[getParent(idx)]) {
                Integer temp = tree[idx];
                tree[idx] = tree[getParent(idx)];
                tree[getParent(idx)] = temp;
            }
            idx = getParent(idx);
        }
    }

    private void siftDown(int idx) {
        while (getLeft(idx) <= lastIdx) {
            if (getRight(idx) > lastIdx) {
                if (tree[idx] > tree[getLeft(idx)]) {
                    Integer temp = tree[idx];
                    tree[idx] = tree[getLeft(idx)];
                    tree[getLeft(idx)] = temp;
                }
                idx = getLeft(idx);
            } else {
                int minChild = tree[getLeft(idx)] < tree[getRight(idx)] ? getLeft(idx) : getRight(idx);
                if (tree[idx] > tree[minChild]) {
                    Integer temp = tree[idx];
                    tree[idx] = tree[minChild];
                    tree[minChild] = temp;
                }
                idx = minChild;
            }
        }
    }

    /**
     * 是否有更好方法
     *
     * @param idx
     * @return
     */
    private int getParent(int idx) {
        if (idx == 0) {
            return -1;
        }
        return (idx - 1) / 2;
    }

    private int getLeft(int idx) {
        return 2 * idx + 1;
    }

    private int getRight(int idx) {
        return 2 * idx + 2;
    }

    public static void main(String[] args) {
        HeapSort heap = new HeapSort();
        int size = 20;
        int range = 999;
        Integer[] array = DataUtil.genUniqueArray(size, range);
        DataUtil.printIndex(size);
        DataUtil.printArray(array);
        DataUtil.printArray(heap.sort(array));
    }

}
